package com.qihe.reviewj2se;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class TestSort {

	public static Integer[] a = { 1, 3, 4, 5, 6, 7, 9, 8, 0, 2 };

	public static void swap(int i, int j) {
		int temp = 0;
		temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	
	public static void swap(int[] a, int i, int j) {
		int temp = 0;
		temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	public static void shuffle() {
		List l = Arrays.asList(a);
		Collections.shuffle(l);
		l.toArray(a);
	}

	public static void print() {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
		System.out.println("TestSort.print()");
	}
	
	public static void print(int[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
		System.out.println("TestSort.print()");
	}

	public static void bubbleSort() {
		for(int i = a.length; i > 1; i--) {
			for(int j = 0; j < i - 1; j++) {
				if(a[j] > a[j+1]) {
					swap(j, j+1);
				}
			}
		}
	}
	
	public static void selectionSort() {
		int out, in, min;
		for(out = 0; out < a.length; out++) {
			min = out;
			for(in = min + 1; in < a.length; in++) {
				if(a[in] < a[min]) {
					min = in;
				}
			}
			swap(min, out);
		}
	}
	
	public static void binarySearch(int i) {
		
	}
	
	public static void insertSort() {
		int out, in, temp;
		for(out = 1; out < a.length; out++) {
			temp = a[out];
			in = out;
			while(in > 0 && a[in - 1] > temp) {
				a[in] = a[in -1];
				in--;
			}
			a[in] = temp;
		}
	}
	
	public static void shellSort() {
		int out, in, temp, h = 1;
		
		while(h < a.length/3) {
			h = h*3 +1;
		}
		
		while(h > 0) {
			for(out = h; out < a.length; out++) {
				temp = a[out];
				in = out;
				while(in > h-1 && a[in-h] > temp) {
					a[in] = a[in - h];
					in -= h;
				}
				a[in] = temp;
			}
			h = (h-1)/3;
		}
	}
	
	public static void fastSort() {
		
		fastSort(0, a.length);
	}
	
	private static void fastSort(int i, int length) {
		int size = length - i + 1;
		if(size <= 3) {
			//medianSort(i, length);
		}
		int pivot = medianOf3();
		int posi = partition(i, length, pivot);
		fastSort(i, posi -1);
		fastSort(posi + 1, length);
	}

	private static int partition(int i, int length, int pivot) {
		int left = i, right = length - 1;
		while(true) {
			while(a[++left] < pivot);
			while(a[--right] > pivot);
			if(left >= right) break;
			swap(left, right);
		}
		swap(left, length - 1);
		return left;
	}

	private static void medianSort(int[] a, int i, int length) {
		int size = length - i + 1;
		if(1 == size) {
			return;
		} else if(2 == size) {
			if(a[i] > a[i + 1]) {
				swap(i, i + 1);
			}
		} else if(3 == size) {
			if(a[i] > a[i + 1]) {
				swap(a, i, i + 1);
			} if(a[i] > a[i + 2]) {
				swap(a, i, i + 2);
			} if(a[i + 1] > a[i + 2]) {
				swap(a, i + 1, i + 2);
			}
		}
	}

	private static int medianOf3() {
		return 0;
	}
	
	public static void main(String[] args) {
		shuffle();
		print();
		//shellSort();
		print();
		int[] a2 = new int[]{2, 1, 3};
		medianSort(a2, 0, 2);
		print(a2);
	}

}
